package DataStructureAndAlgorithm.Acwing.DP.最长子序列DP;
//902. 最短编辑距离
/*
动态数组dp[word1.length+1][word2.length+1]

dp[i][j]表示从word1前i个字符转换到word2前j个字符最少的步骤数。

假设word1现在遍历到字符x，word2遍历到字符y（word1当前遍历到的长度为i，word2为j）。

以下两种可能性：

    x==y，那么不用做任何编辑操作，所以dp[i][j] = dp[i-1][j-1]

    x != y

(1) 在word1插入y， 那么dp[i][j] = dp[i][j-1] + 1

(2) 在word1删除x， 那么dp[i][j] = dp[i-1][j] + 1

(3) 把word1中的x用y来替换，那么dp[i][j] = dp[i-1][j-1] + 1

最少的步骤就是取这三个中的最小值。

最后返回 dp[word1.length+1][word2.length+1] 即可。

 */
import java.util.Scanner;
public class dp_902 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n, m;
        String a, b;
        n = in.nextInt();
        a = in.next();
        m = in.nextInt();
        b = in.next();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= m; i++) dp[0][i] = i;//初始化增加的操作数
        for (int i = 0; i <= n; i++) dp[i][0] = i;//初始化修改的操作数
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                //[i-1][j]:表示a中的前i-1个字母和b中的前j个字母相同，即删除操作
                //[i][j-1]:表示a中前i个字母和b中前j-1个字母相同，即增加操作
                if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                else dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + 1);
                //最后这个if判断的是两个字符串在i和j的位置是否相同，如果相同，则不加1，否则，加1
            }
        }
        System.out.print(dp[n][m]);
    }
}
/*
给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B

，可进行的操作有：

    删除–将字符串 A

中的某个字符删除。
插入–在字符串 A
的某个位置插入某个字符。
替换–将字符串 A

    中的某个字符替换为另一个字符。

现在请你求出，将 A
变为 B

至少需要进行多少次操作。
输入格式

第一行包含整数 n
，表示字符串 A

的长度。

第二行包含一个长度为 n
的字符串 A

。

第三行包含整数 m
，表示字符串 B

的长度。

第四行包含一个长度为 m
的字符串 B

。

字符串中均只包含大写字母。
输出格式

输出一个整数，表示最少操作次数。
数据范围

1≤n,m≤1000

输入样例：

10
AGTCTGACGC
11
AGTAAGTAGGC

输出样例：

4

 */